package a12_图论;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * <p>
 * a03_所有可达路径复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/3/18
 */
public class a03_所有可达路径复习2 {
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//
//        int num = scanner.nextInt();
//        int totalSides = scanner.nextInt();
//
//        int[][] sides = new int[num+1][num+1];
//        for (int i = 0; i < totalSides; i++) {
//            int x = scanner.nextInt();
//            int y = scanner.nextInt();
//            sides[x][y] = 1;
//        }


        int num = 5;
        int totalSides = 5;

        int[][] sides = new int[num+1][num+1];
        sides[1][3] = 1;
        sides[3][5] = 1;
        sides[1][2] = 1;
        sides[2][4] = 1;
        sides[4][5] = 1;

        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        path.add(1);
        dfs(result, path, sides, 1);
        if (result.isEmpty()) {
            System.out.println(-1);
        }else {
            for (List<Integer> list : result) {
                for (int i = 0; i < list.size(); i++) {
                    System.out.print(list.get(i));
                    if(i != list.size()-1){
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }

    }

    private static void dfs(List<List<Integer>> result,
                            LinkedList<Integer> path,
                            int[][] sides,
                            int startIdx){

        if(startIdx == sides.length-1){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 1; i < sides[startIdx].length; i++) {
            if(sides[startIdx][i] == 0){
                continue;
            }
            path.add(i);
            dfs(result, path, sides, i);
            path.removeLast();
        }
    }
}
